package array;

/**
 * 二分查找
 * 问：
 *  给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 * 前提：
 *  1.数组中的所有元素是不重复（有重复元素，使用二分查找法返回的元素下标可能不是唯一）
 *  2.数组为有序数组（无序则无法二分查找）
 * 示例 1:
 *  输入: nums = [-1,0,3,5,9,12], target = 9
 *  输出: 4
 *  解释: 9 出现在 nums 中并且下标为 4
 * 思路：
 *  因为有序，所以取数组中间位置的值与目标数做对比，通过大于或小于，将区间分为左右两个子区间，然后继续在子区间里根据中间值查找。
 *  查找范围：[0, n-1] 或 [0, 1)
 *  <br>
 *  <img src="https://code-thinking-1253855093.file.myqcloud.com/pics/20210311153055723.jpg" alt=""/>
 *  <br>
 * 时空：
 *  时间复杂度：O(log n)
 *  空间复杂度：O(1)
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int result =  binarySearch1Solution(nums, 6);
        System.out.println("result = " + result);
    }

    private static int binarySearch1(int[] nums, int target) {

        // 定义target在左闭右闭的区间里，[left, right]

        // 当left==right，区间[left, right]依然有效，所以用 <=

            // 防止溢出 等同于(left + right)/2


                // target 在左区间，所以[left, middle - 1]


                // target 在右区间，所以[middle + 1, right]


                // nums[middle] == target
                // 数组中找到目标值，直接返回下标



        // 未找到目标值
        return -1;
    }

    private static int binarySearch1Solution(int[] nums, int target) {
        // 定义target在左闭右闭的区间里，[left, right]
        int left = 0;
        int right = nums.length - 1; //right = nums.length 区间则为[left, right)
        // 当left==right，区间[left, right]依然有效，所以用 <=
        while (left <= right) {
            // 防止溢出 等同于(left + right)/2
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                // target 在左区间，所以[left, middle - 1]
                right = middle - 1;
            }else if (nums[middle] < target) {
                // target 在右区间，所以[middle + 1, right]
                left = middle + 1;
            }else {
                // nums[middle] == target
                // 数组中找到目标值，直接返回下标
                return middle;
            }
        }
        // 未找到目标值
        return -1;
    }
}
